package com.captain.special.链表;

import com.captain.leetcode.链表.ListNode;

/**
 * Des:
 *
 * @author XL
 * @Date 2022/3/23 14:26
 */
public class 分隔链表86 {
    public static void main(String[] args) {
        new 分隔链表86().partition(ListNode.getInstance(), 3);
    }

    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) return head;
        ListNode small = new ListNode(-1);
        //操作链表
        ListNode curSmall = small;
        //操作链表
        ListNode large = new ListNode(-1);
        ListNode curLarge = large;
        //操作数据 1,4,3,2,5,2  3
        while (head != null) {
            int val = head.val;
            //左边为小,右边为大
            if (val < x) {
                curSmall.next = head;
                curSmall = curSmall.next;
            } else {
                curLarge.next = head;
                curLarge = curLarge.next;
            }
            head = head.next;
        }
        //处理最后一个值,如果最后一个值比x小, 则需要将大的值置为null,不然形成死循环
        curLarge.next = null;
        curSmall.next = large.next;
        return small.next;
    }
}
